4786. Отрезки

 

Даны отрезки на прямой. Какое максимальное количество отрезков можно выбрать так, чтобы никакие два из них не пересекались? Отрезки считаются открытыми.

 

Вход. В первой строке задано количество отрезков n (1 ≤ n ≤ 105). В каждой из следующих n строк содержатся два целых числа li и ri (1 ≤ li < ri ≤ 109) – координаты начала и конца i-го отрезка.

 

Выход. Выведите максимальное количество непересекающихся отрезков.

 

Пример входа 1

Пример выхода 1

5

1 4

3 8

7 8

2 5

4 6

3

 

 

Пример входа 2

Пример выхода 2

4

1 3

2 6

1 8

2 5

1

 

 

РЕШЕНИЕ

жадность – выбор заявок

 

Анализ алгоритма

Отсортируем отрезки по их правым концам. Выберем первый отрезок и удалим все пересекающиеся с ним отрезки. Затем выберем следующий самый левый отрезок и снова удалим пересекающиеся с ним. Используя такой жадный алгоритм, мы выберем максимальное количество непересекающихся отрезков.

 

Реализация алгоритма

Объявим класс segment, который будет хранить интервал [start; fin).

 

class segment

{

public:

  int start, fin;

  segment(int start, int fin) : start(start), fin(fin) {}

};

 

Набор входных интервалов сохраняем в векторе v.

 

vector<segment> v;

 

Функция f является компаратором для сортировки интервалов по возрастанию их правых концов.

 

int f(segment a, segment b)

{

  return a.fin < b.fin;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d", &n);

while (n--)

{

  scanf("%d %d", &a, &b);

  v.push_back(segment(a, b));

}

 

Сортируем отрезки.

 

sort(v.begin(), v.end(), f);

 

Пусть текущий обрабатываемый интервал содержится в переменной cur. Начнем алгоритм с нулевого интервала, установив cur = 0. В переменной res будем подсчитывать количество выбранных интервалов. Поскольку нулевой интервал изначально выбран, установим res = 1.

 

cur = 0; res = 1;

 

Перебираем интервалы, начиная с i = 1.

 

for (i = 1; i < v.size(); i++)

{

 

Для каждого интервала ищем тот, у которого начало не меньше конца текущего cur. Как только такой интервал найден, выбираем его и присваиваем cur номер этого нового интервала.

 

  if (v[i].start >= v[cur].fin)

  {

    cur = i;

    res++;

  }

}

 

Выводим максимальное количество непересекающихся интервалов.

 

printf("%d\n", res);

 

Java реализация

 

import java.util.*;

 

class Segment

{

  int start, fin;

 

  public Segment(int start, int fin)

  {

    this.start = start;

    this.fin = fin;

  }

}

 

public class Main

{

  public static class MyFun implements Comparator<Segment>

  {

    public int compare(Segment a, Segment b)

    {

      return a.fin - b.fin;

    }

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    ArrayList<Segment> seg = new ArrayList<Segment>();   

 

    for (int i = 0; i < n; i++)

    {

      int a = con.nextInt();

      int b = con.nextInt();

      seg.add(new Segment(a,b)); 

    }

     

    Collections.sort(seg, new MyFun());   

   

    int cur = 0, res = 1;

    for (int i = 1; i < seg.size(); i++)

    {

      if (seg.get(i).start >= seg.get(cur).fin)

      {

        cur = i;

        res++;

      }

    }

   

    System.out.println(res);

    con.close();

  }

}